package Offer;

//33.二叉搜索树的后序遍序历序列
public class Offer33 {
    public boolean verifyPostorder(int[] postorder) {
        //二叉搜索树：左小右大
        //后序遍历：左右中
        //逆后序遍历：中右左
        //结论：逆后序遍历的第一个数是整个树的根节点
        //``对于每个根节点，第一个比它大的数是其右节点 右子树范围为(左根节点，右根节点)
        //``对于每个根节点，第一个比他小的数是其左节点 左子树范围为(0,左根节点)
        //左根节点必须在右根节点的前面
        //只需判断每个子树是否递归的满足该结论
        if(postorder.length<2)
            return true;
        return verify(postorder);
    }

    public boolean verify(int[] post) {
        //寻找右节点
        int value = post[post.length - 1];
        int right, left;
        for (right = post.length - 2; right >= 0; right--) {
            if (post[right] > value)
                break;
        }
        //寻找左节点
        for (left = post.length - 2; left >= 0; left--) {
            if (post[left] < value)
                break;
        }
        if (right >= 0 && left >= 0 && left > right)
            return false;
        boolean l = true, r = true;
        //递归右子树
        int count = 0;
        if (right >= 0) {
            count = right - left - 1;
            if (count > 0) {
                int[] p = new int[count + 1];
                for (int i = left + 1, j = 0; i < right + 1; i++, j++) {
                    p[j] = post[i];
                }
                r = verify(p);
            }
        }
        //递归左子树
        if (left >= 0) {
            count = left;
            if (count > 0) {
                int[] p = new int[count + 1];
                for (int i = 0, j = 0; i < left + 1; i++, j++) {
                    p[j] = post[i];
                }
                //根节点应该比左子树的全部元素都要大
                for (int i = 0; i < p.length; i++) {
                    if (p[i] > value)
                        return false;
                }
                l = verify(p);
            }
        }

        return l && r;
    }

    //-------错误思路：每次都可以把第一个元素当做"左"，第二个元素当做"中"或者"右"-------
    /*
    public boolean verifyPostorder(int[] postorder) {
        //二叉搜索树：左小右大
        //后序遍历：左右中
        //如果第二个元素当做"中",则下一次判断时"左"为该元素
        //如果第二个元素当做"右"，则下一次判断时"左"为第三个元素
        int index = 0;
        while (index < postorder.length) {
            //如果当前是左中结构
            if (leftMidume(postorder, index)) {
                index++;
                continue;
            }
            //如果当前是左中右结构
            else if (leftRightMidume(postorder, index)) {
                index += 2;
                continue;
            }
            //如果都不满足，则直接返回false
            return false;
        }
        return true;
    }

    public boolean leftMidume(int[] postorder, int index) {
        //index为"左"
        //如果下标越界说明应该返回true
        try {
            if (postorder[index] < postorder[index + 1]) {
                if (postorder[index + 1] > postorder[index + 2]) {
                    return false;
                } else {
                    return true;
                }
            } else {
                return false;
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            return true;
        }
    }

    public boolean leftRightMidume(int[] postorder, int index) {
        //index为"左"
        //如果下标越界说明应该返回true
        try {
            if (postorder[index] < postorder[index + 1]) {
                if (postorder[index] < postorder[index + 2] && postorder[index + 1] > postorder[index + 2]) {
                    return true;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            return true;
        }
    }
    */
    public static void main(String[] args) {
        Offer33 offer33 = new Offer33();
        boolean a = offer33.verifyPostorder(new int[]{4, 8, 6, 12, 16, 14, 10});
        System.out.println(a);
        boolean b = offer33.verifyPostorder(new int[]{4, 6, 7, 5});
        System.out.println(b);
        boolean c = offer33.verifyPostorder(new int[]{7, 4, 6, 5});
        System.out.println(c);

    }

}
